package class03;

// 本题测试链接 : https://leetcode.com/problems/largest-1-bordered-square/
public class Code03_Largest1BorderedSquare {

	// 主函数：寻找矩阵中最大的边界为1的正方形面积
	// 参数m是一个二维数组，只包含0和1
	// 返回值是边界全为1的最大正方形的面积
	public static int largest1BorderedSquare(int[][] m) {
		// 创建两个辅助数组记录每个位置向右和向下连续1的个数
		int[][] right = new int[m.length][m[0].length];
		int[][] down = new int[m.length][m[0].length];
		// 初始化辅助数组
		setBorderMap(m, right, down);
		// 从最大可能的边长开始尝试，逐步减小
		for (int size = Math.min(m.length, m[0].length); size != 0; size--) {
			// 检查是否存在指定大小的边界为1的正方形
			if (hasSizeOfBorder(size, right, down)) {
				// 找到满足条件的最大正方形，返回其面积
				return size * size;
			}
		}
		// 没有找到边界为1的正方形
		return 0;
	}

	// 预处理函数：计算每个位置向右和向下连续1的个数
	// 参数m是原始矩阵
	// 参数right记录每个位置向右连续1的个数
	// 参数down记录每个位置向下连续1的个数
	/*
	示例验证
	对于矩阵：
	[1,1,1]
	[1,0,1]
	[1,1,1]
	预处理后：right数组
	[3,2,1]  // 第0行：从(0,0)向右有3个1，(0,1)向右有2个1，(0,2)向右有1个1
	[1,0,1]  // 第1行：从(1,0)向右有1个1，(1,1)是0，(1,2)向右有1个1
	[3,2,1]  // 第2行：从(2,0)向右有3个1，(2,1)向右有2个1，(2,2)向右有1个1
	最终down数组：
	[3,1,3]  // 第0行：从(0,0)向下有3个1，(0,1)向下有1个1，(0,2)向下有3个1
	[2,0,2]  // 第1行：从(1,0)向下有2个1，(1,1)是0，(1,2)向下有2个1
	[1,1,1]  // 第2行：从(2,0)向下有1个1，(2,1)向下有1个1，(2,2)向下有1个1
	 */
	public static void setBorderMap(int[][] m, int[][] right, int[][] down) {
		int r = m.length;
		int c = m[0].length;
		// 处理右下角位置
		if (m[r - 1][c - 1] == 1) {
			right[r - 1][c - 1] = 1;
			down[r - 1][c - 1] = 1;
		}
		// 处理最后一列（除右下角外）
		for (int i = r - 2; i != -1; i--) {
			if (m[i][c - 1] == 1) {
				right[i][c - 1] = 1;
				// 向下的连续1个数等于下方位置的值加1
				down[i][c - 1] = down[i + 1][c - 1] + 1;
			}
		}
		// 处理最后一行（除右下角外）
		for (int i = c - 2; i != -1; i--) {
			if (m[r - 1][i] == 1) {
				// 向右的连续1个数等于右方位置的值加1
				right[r - 1][i] = right[r - 1][i + 1] + 1;
				down[r - 1][i] = 1;
			}
		}
		// 处理其余位置：从右下向左上遍历
		for (int i = r - 2; i != -1; i--) {
			for (int j = c - 2; j != -1; j--) {
				if (m[i][j] == 1) {
					// 向右的连续1个数等于右方位置的值加1
					right[i][j] = right[i][j + 1] + 1;
					// 向下的连续1个数等于下方位置的值加1
					down[i][j] = down[i + 1][j] + 1;
				}
			}
		}
	}

	// 检查函数：检查是否存在边长为size且边界全为1的正方形
	// 参数size是要检查的正方形边长
	// 参数right是预处理得到的向右连续1个数的数组
	// 参数down是预处理得到的向下连续1个数的数组
	// 返回值表示是否存在这样的正方形
	public static boolean hasSizeOfBorder(int size, int[][] right, int[][] down) {
		// 遍历所有可能作为正方形左上角顶点的位置
		for (int i = 0; i != right.length - size + 1; i++) {
			for (int j = 0; j != right[0].length - size + 1; j++) {
				// 检查四个边是否都满足条件：
				// 1. 上边：起点[right[i][j]]向右连续1的个数>=size
				// 2. 左边：起点[down[i][j]]向下连续1的个数>=size
				// 3. 下边：起点[right[i + size - 1][j]]向右连续1的个数>=size
				// 4. 右边：起点[down[i][j + size - 1]]向下连续1的个数>=size
				if (right[i][j] >= size && down[i][j] >= size && right[i + size - 1][j] >= size
						&& down[i][j + size - 1] >= size) {
					// 找到满足条件的正方形
					return true;
				}
			}
		}
		// 没有找到满足条件的正方形
		return false;
	}

}
